<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>正则表达式2</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="正则表达式2">正则表达式2</h1>
<ul>
<li>
<ol start="44">
<li>Wildcard Matching</li>
</ol>
</li>
<li><a href="https://leetcode.com/problems/wildcard-matching/">https://leetcode.com/problems/wildcard-matching/</a></li>
</ul>
<h2 id="1-introduce">1. introduce</h2>
<pre><code><code><div>Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:
Input:
s = &quot;aa&quot;
p = &quot;a&quot;
Output: false
Explanation: &quot;a&quot; does not match the entire string &quot;aa&quot;.

Example 2:
Input:
s = &quot;aa&quot;
p = &quot;*&quot;
Output: true
Explanation: '*' matches any sequence.

Example 3:
Input:
s = &quot;cb&quot;
p = &quot;?a&quot;
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:
Input:
s = &quot;adceb&quot;
p = &quot;*a*b&quot;
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring &quot;dce&quot;.

Example 5:
Input:
s = &quot;acdcb&quot;
p = &quot;a*c?b&quot;
Output: false

本题有一个可以提高速度的技巧， 就是针对 &quot;a**b****c&quot;这样的pattern  做预处理，变成 &quot;a*b*c&quot;

</div></code></code></pre>
<h2 id="12-我的第一个版本-必须结合lru_cache不然会超时">1.2 我的第一个版本, 必须结合lru_cache,不然会超时</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>

<span class="hljs-meta">    @lru_cache(None)</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> p == <span class="hljs-string">""</span>: <span class="hljs-keyword">return</span> s == <span class="hljs-string">""</span>

        <span class="hljs-keyword">if</span> p[<span class="hljs-number">0</span>]==<span class="hljs-string">"*"</span>:
            <span class="hljs-keyword">if</span> self.isMatch(s, p[<span class="hljs-number">1</span>:]): <span class="hljs-comment"># * match nothing</span>
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> s <span class="hljs-keyword">and</span> self.isMatch(s[<span class="hljs-number">1</span>:], p[<span class="hljs-number">1</span>:]): <span class="hljs-comment"># * match one</span>
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> s <span class="hljs-keyword">and</span> self.isMatch(s[<span class="hljs-number">1</span>:], p):  <span class="hljs-comment"># * match multi</span>
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">elif</span> s <span class="hljs-keyword">and</span> (p[<span class="hljs-number">0</span>]==<span class="hljs-string">"?"</span> <span class="hljs-keyword">or</span> p[<span class="hljs-number">0</span>]==s[<span class="hljs-number">0</span>]):
            <span class="hljs-keyword">if</span> self.isMatch(s[<span class="hljs-number">1</span>:], p[<span class="hljs-number">1</span>:]):
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
</div></code></pre>
<h2 id="13-答案里面效率最高的版本">1.3 答案里面效率最高的版本</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> p: <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        i, j = <span class="hljs-number">0</span>, <span class="hljs-number">0</span>
        lens, lenp = len(s), len(p)
        startIndex = <span class="hljs-number">-1</span>
        match = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> i &lt; lens:
            <span class="hljs-keyword">if</span> j &lt; lenp <span class="hljs-keyword">and</span> (s[i] == p[j] <span class="hljs-keyword">or</span> p[j] == <span class="hljs-string">"?"</span>):
                i += <span class="hljs-number">1</span>
                j += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> j &lt; lenp <span class="hljs-keyword">and</span> p[j] == <span class="hljs-string">"*"</span>:
                startIndex = j
                match = i
                j += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> startIndex != <span class="hljs-number">-1</span>:
                j = startIndex + <span class="hljs-number">1</span>
                match += <span class="hljs-number">1</span>
                i = match
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">while</span> j &lt; lenp <span class="hljs-keyword">and</span> p[j] == <span class="hljs-string">"*"</span>:
            j += <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> j == lenp
</div></code></pre>
<h1 id="14-bottom-to-top-dp">1.4 bottom to top, dp</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=3ZDZ-N0EPV0&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=24">https://www.youtube.com/watch?v=3ZDZ-N0EPV0&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=24</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/WildCardMatching.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/WildCardMatching.java</a></li>
</ul>
<p>看了tushare roy的youtube视频以后，写了dp解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> s==<span class="hljs-literal">None</span> <span class="hljs-keyword">or</span> p==<span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        
        m = len(s)
        n = len(p)
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>)]
        dp[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = <span class="hljs-literal">True</span>
        
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">if</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"*"</span>:
                dp[<span class="hljs-number">0</span>][j] = dp[<span class="hljs-number">0</span>][j<span class="hljs-number">-1</span>]
                
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> s[i<span class="hljs-number">-1</span>] == p[j<span class="hljs-number">-1</span>] <span class="hljs-keyword">or</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"?"</span>:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">elif</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"*"</span>:
                    <span class="hljs-keyword">if</span> dp[i][j<span class="hljs-number">-1</span>]:       <span class="hljs-comment"># case 1, * match 0</span>
                        dp[i][j] = <span class="hljs-literal">True</span>
                    <span class="hljs-keyword">elif</span> dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]:   <span class="hljs-comment"># case 2, * match one, 这个case2可以不用处理</span>
                        dp[i][j] = <span class="hljs-literal">True</span>
                    <span class="hljs-keyword">elif</span> dp[i<span class="hljs-number">-1</span>][j]:     <span class="hljs-comment"># case 3, * match multi</span>
                        dp[i][j] = <span class="hljs-literal">True</span>
                        
        <span class="hljs-keyword">return</span> dp[m][n]
</div></code></pre>
<p>还可以改进一下, 但提交以后，耗时反而更长了一点。。。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> s==<span class="hljs-literal">None</span> <span class="hljs-keyword">or</span> p==<span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        
        m = len(s)
        n = len(p)
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>)]
        dp[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = <span class="hljs-literal">True</span>
        
        <span class="hljs-comment"># handle *a, **b*c* d*f**</span>
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">if</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"*"</span>:
                dp[<span class="hljs-number">0</span>][j] = dp[<span class="hljs-number">0</span>][j<span class="hljs-number">-1</span>]
                
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> s[i<span class="hljs-number">-1</span>] == p[j<span class="hljs-number">-1</span>] <span class="hljs-keyword">or</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"?"</span>:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">elif</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"*"</span>:
                    dp[i][j] = dp[i][j<span class="hljs-number">-1</span>] | dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>] | dp [i<span class="hljs-number">-1</span>][j]
                        
        <span class="hljs-keyword">return</span> dp[m][n]
    
</div></code></pre>

    </body>
    </html>